1. Technical Field
The present invention relates to a computer resources access control apparatus and method for controlling access by each process/thread to a shared resource in a system in which a plurality of processes or threads gain an access to a shared computer resource for processing.
More specifically, the present invention relates to a computer resources access control apparatus and method for controlling write access by each processing element to a VRAM so that a regular processing result is finally obtained in an image processing system in which each of a plurality of image processing processor elements (PE) writes image data having an overlapped areas to a shared computer resource (video RAM, i.e., VRAM).
2. Prior Art
When, for example, a plurality of processes or threads process in parallel using a shared data resource (shared resource), an inexpedience or a contradiction in processing could be invited wherein, for example, data written by a process/thread in a portion of a shared resource is destructed by another process/thread writing data to the same portion.
Thus, in a parallel processing system in which a plurality of process/threads gain an access to a shared resources and process in parallel, a restricting control is needed to allow only one of the plurality of process/threads to gain an access to one portion of the shared resource while inhibiting any other process/threads from gaining an access to this portion simultaneously. A computer system which effects a control to limit a portion to which a plurality of process/threads can gain an access simultaneously is called a synchronous computer system.
A method of access control among a plurality of process/threads in the above described synchronous computer system includes a mutual exclusion (hereinafter called MUTEX) method which simply controls access by a plurality of process/threads to a shared resource on an exclusive base, and a semaphore method based in a more complex control, for example. In the synchronous computer system, these methods are implemented so as not to invite an inexpedience inherent to the synchronous computer system among process/threads such as a deadlock or starvation. The above starvation is a phenomenon in which, in an attempt by a process/thread to gain an access to one of a plurality of portions on a memory, an inaccessible time period sustains for a long time because an exclusive control is applied to another overlapped portion. Assuming a portion C partly overlapping a portion A and a portion B (portions A and B do not overlap) as a specific example, states (a) , . . . (f) shown in Table 1 below may continue to loop resulting in a starvation so that a process/thread can never gain an access to the portion C.
Table 1--Specific Example of Starvation
(a) The portion C may not be locked while the portion A stays locked. PA1 (b) If lock is requested to the portion B, the portion B may be locked because it does not overlap the portion A. PA1 (c) Even if the portion A is unlocked, the portion C overlapping the portion B which was locked in (b) can not be locked. PA1 (d) The portion C may not be locked while the portion B stays locked PA1 (e) If lock is requested to the portion A, it may be locked because it does not overlap the portion B. PA1 (f) Even if the portion B is unlocked, the portion C overlapping the portion A which was locked in (e) may not be locked. PA1 exclusive access permission control means, operative when said processing means requests an exclusive access to said portion while an exclusive access to other one or more of said portions having an area overlapping said portion to which said processing means requested an exclusive access is not permitted, for permitting said processing means requesting the exclusive access to gain an exclusive access to said portion, PA1 a plurality of counting means provided in correspondence to each of said portions for counting the number of said exclusive accesses permitted to said other one or more portions having an area overlapping the corresponding one of said portions for each period in which said exclusive access to corresponding one of said portions is requested while said exclusive access to the corresponding one of said portions is not permitted, and PA1 access inhibiting control means for inhibiting permission of an exclusive access to said other one or more portions having an area overlapping said portion corresponding to said counting means when the count of said counting means reaches a predetermined value. PA1 permitting said processing means requesting the exclusive access to gain an exclusive access to said portion when said processing means requests an exclusive access to said portion while an exclusive access to other one or more of said portions having an area overlapping said portion to which said processing means requested an exclusive access in not permitted, PA1 counting the number of said exclusive accesses permitted to said other one or more portions having an area overlapping corresponding one of said portions for each period in which said exclusive access to corresponding one of said portions is requested and said exclusive access to the corresponding one of said portions is not permitted and, PA1 inhibiting permission of an exclusive access to said other one or more portions having an area overlapping said portion in which said count reaches a predetermined value. PA1 permitting said processing means requesting the exclusive access to gain an exclusive access to said portion when said processing means requests an exclusive access to said portion while an exclusive access to other one or more of said portions having an area overlapping said portion to which said processing means requested an exclusive access is not permitted, PA1 counting the number of said exclusive accesses permitted to said other one or more portions having an area overlapping corresponding one of said portions for each period in which said exclusive access to corresponding one of said portions is requested and said exclusive access to the corresponding one of said portions is not permitted, and PA1 inhibiting permission of an exclusive access to said other one or more portions having an area overlapping said portion in which said count reaches a predetermined value.
In the above, "lock" means a state in which an access to a portion x by one of processing means operating in parallel is permitted while an access to the portion x by other processing means is inhibited and "unlock" means a state in which a locked state is released from locking.
In the area of image processing, a process of generating a final image from data is called "rasterize". Conventionally, a prior art rasterizing device used to have only one image processing means per unit so that a rasterizing process was performed in the sequence specified by input data without parallel processing performed. Accordingly, the rasterizing process was always performed in the sequence specified by data so that there was no chance where the finally obtained image contained an error due to disordered sequence of processing.
However, a device which processes rasterizing by using a plurality of image processing means has been advent in recent years in which the sequence of processing data could be disordered among the image processing means resulting in an error in the finally obtained image. For example, when it is necessary to draw a rectangular image overlapped on a circular image, a correct image can be obtained by drawing the rectangular image after the circular image has been drawn while a correct image can not be obtained if the circular image is drawn after the rectangular image has been drawn. In other words, a plurality of processing threads must not simultaneously write to an overlapped areas of a portion of a shared resource.
Further, there is a rasterize processing method such as HTML (HyperText Markup Language) in which stored data is taken out part by part as needed for rasterize processing rather than controlling the entire data as a single data stream. In using such method, it is necessary to process the data satisfying a requirement first to shorten the time of rasterize processing rather than processing the data in the specified sequence.
In rasterize processing using a plurality of process/threads, it is the simplest way to have each process/thread rasterize different portions in parallel. However, when each process/thread is going to rasterize in parallel in the above described synchronous computer system, necessary processing performance may not be available or a memory of huge capacity may be needed.
Such inexpediency is further described with reference to a specific example.
When a method of locking the entire VRAM for image preparation by a single MUTEX is employed in rasterize processing using a plurality of process/threads, only a single process/thread can process rasterizing at one time. The parallelism of rasterize processing is thus harmed and a high processing performance can not be obtained.
Also, when a method of locking pixel by pixel using MUTEX in rasterize processing using a plurality of process/threads, a number of MUTEX processing corresponding to the number of pixels constituting an image are required. Thus, a huge capacity of a memory is needed and, in addition, a long time is required for locking and unlocking processes by MUTEX so that a high processing performance can not be obtained.
When a method of exclusively controlling each portion to be rasterized using semaphore (a synchronous computer system stores locked portions and, upon occurrence of a new request to lock a predetermined portion, permits to lock only a portion which does not overlap another portion which is already locked) is employed in rasterize processing using a plurality of process/threads, the above described starvation may occur so that a high performance may not be obtained.
The present invention was conceived in view of the above described problems in the prior art and has a purpose of providing a computer resource access control apparatus and method which assure a correct processing result to be obtained without causing a starvation when a plurality of processing threads gain an access to a shared computer resource such as a VRAM for rasterize processing in a synchronous computer system and further assures a high processing performance using a memory of reasonable capacity.